package com.codingxyz.simple.algorithm;


/**
 * 排序算法
 */
public class ASort {


    /**
     * 插入排序法
     * 首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
     * 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
     * 从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
     * 将当前数放置到空着的位置，即j+1。
     * @param data
     * @return
     */
    public void insertSort(Integer data[]){

        if(data.length==0){
            throw new RuntimeException("数据长度为空");
        }

        for(int i=1;i<data.length;i++){

            int insertNum = data[i];

            int j=i-1;
            while (j>=0&&data[j]>insertNum){
                data[j+1] = data[j];
                j--;
            }
            data[j+1] = insertNum;
        }

    }

    /**
     * 冒泡排序法
     * 将序列中所有元素两两比较，将最大的放在最后面。
     * 将剩余序列中所有元素两两比较，将最大的放在最后面。
     * 重复第二步，直到只剩下一个数。
     * @param data
     * @return
     */
    public void bubbleSort(Integer[] data){

        if(data.length==0){
            throw new RuntimeException("数据长度为空");
        }

        int len = data.length;
        for(int i=0;i<len;i++){

            int tmp;
            for(int j = 0;j<len-i-1;j++){

                if(data[j]>data[j+1]){
                    tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;
                }
            }

        }
    }


    /**
     * 快速排序法
     * 要求时间最快时。
     * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
     * 递归的将p左边和右边的数都按照第一步进行，直到不能递归。
     * @param data
     * @return
     */
    public void fastSort(Integer[] data){

        if(data.length==0){
            throw new RuntimeException("数据长度为空");
        }

        Integer node = data[0];

        for(int i=1;i<data.length;i++){
            if(data[i]<node){
                data[i-1] =data[i];
                data[i] = node;
            }
        }
    }

    public void quickSort(Integer[]a,int start,int end){
        if(start<end){
            int baseNum=a[start];//选基准值
            int midNum;//记录中间值
            int i=start;
            int j=end;
            do{
                while((a[i]<baseNum)&&i<end){
                    i++;
                }
                while((a[j]>baseNum)&&j>start){
                    j--;
                }
                if(i<=j){
                    midNum=a[i];
                    a[i]=a[j];
                    a[j]=midNum;
                    i++;
                    j--;
                }
            }while(i<=j);
            if(start<j){
                quickSort(a,start,j);
            }
            if(end>i){
                quickSort(a,i,end);
            }
        }
    }

    public int getMiddle(Integer[] list, int low, int high) {
        int tmp = list[low];    //数组的第一个作为中轴
        while (low < high) {
            while (low < high && list[high] > tmp) {
                high--;
            }
            list[low] = list[high];   //比中轴小的记录移到低端
            while (low < high && list[low] < tmp) {
                low++;
            }
            list[high] = list[low];   //比中轴大的记录移到高端
        }
        list[low] = tmp;              //中轴记录到尾
        return low;                   //返回中轴的位置
    }

    public void _quickSort(Integer[] list, int low, int high) {
        if (low < high) {
            int middle = getMiddle(list, low, high);  //将list数组进行一分为二
            _quickSort(list, low, middle - 1);        //对低字表进行递归排序
            _quickSort(list, middle + 1, high);       //对高字表进行递归排序
        }
    }


    public static void main(String[] args) {

        ASort aSort = new ASort();

        Integer[] data = {23,43,32,54,12,65,37};
        aSort._quickSort(data,0,data.length-1);
        System.out.println(aSort.arrayToStr(data));

    }

    public String arrayToStr( Integer[] data){

        StringBuilder stringBuilder = new StringBuilder();

        for (Integer x:data) {
            stringBuilder.append(x+",");
        }

        return stringBuilder.toString();
    }

}
